package com.shr.leetcode;

public class KMP {
	private static int KMPExcute(String text, String pattern){
		int[] next = new int[pattern.length()] ;
		next[0] = -1;
		int k = -1;
		for(int p = 1; p<pattern.length(); p++){
			while(k>-1 && pattern.charAt(k+1)!=pattern.charAt(p))
				k = next[k] ;
			if(pattern.charAt(k+1) == pattern.charAt(p))
				k++ ;
			next[p] = k;
		}
		
		k = -1;
		for(int i = 0;i<text.length();i++){
			while(k > -1 && text.charAt(i)!=pattern.charAt(k+1))
				k = next[k] ;
			if(pattern.charAt(k+1) == text.charAt(i))
				k++;
			if(k == pattern.length()-1)
				return i-k;
				
		}
		
		return -1;
	}
	
	public static void main(String[] args) {
		String text = "abcbacbabcabacbacabacbacbbccaacbacb" ;
		String pattern = "a" ;
		System.out.println(KMPExcute(text, pattern)) ;
	}
}
